package algorithm.niuke;

public class D解码方法 {
    /*
     * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
     * 
     * 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。
     * 
     * 示例 1:
     * 
     * 输入: "12" 输出: 2 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。 示例 2:
     * 
     * 输入: "226" 输出: 3 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
     */
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        char[] chs = s.toCharArray();
        int[] sum = new int[len + 2];
        if (chs[0] >= '1' && chs[0] <= '9') {
            sum[1] = 1;
        }
        sum[0] = 1;
        for (int i = 1; i < len; i++) {
            char pre = chs[i - 1];
            char cur = chs[i];
            if ((pre == '1' ) || (pre == '2' && cur <= '6')) {
                sum[i + 1] += sum[i - 1];
            }
            if (cur >= '1' && cur <= '9') {
                sum[i + 1] += sum[i];
            }
        }
        return sum[len];
    }
}
